package fun.coding.sort;

import java.util.PriorityQueue;

public class SortAlgorithmImpl implements SortAlgorithm {

    /*
     * FIXME: This implementation has bugs, but i get the idea of this question. 
     * http://www.algolist.net/Algorithms/Sorting/Quicksort
     * (non-Javadoc)
     * @see interview.coding.sort.SortAlgorithm#quickSort(int[], int, int)
     */
    @Override
    public void quickSort(int[] array, int left, int right) {
        
        int pos = partition(array, left, right);
        
        if(left < pos - 1)
            quickSort(array, left, pos - 1);
        
        if(right > pos + 1)
        	quickSort(array, pos + 1, right);
        
        
    }
    
    private int partition(int[] array, int left, int right) {
        int pivotIndex = left + (right - left) / 2;
        int pivot = array[pivotIndex];
        swap(array, right, pivotIndex);
        
        int i = left;
        int j = right - 1;
        
        while(i <= j) {
            while(array[i] <= pivot) {
                i++;
            }
            
            while(array[j] >= pivot) {
                j--;
            }
            
            if(i <= j) {
                swap(array, i, j);
                i++;
                j--;
            }
        }
        
        swap(array, i, right);
        return i;
        
    }
    
    private void swap(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

    @Override
    public void mergeSort(int[] array, int left, int right) {
        
        if(left < right) {
            int mid = left + (right - left) / 2;
            
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            merge(array, left, right, mid);
            
        }
        
    }
    
    private void merge(int[] array, int left, int right, int mid) {
        int[] b = new int[right - left + 1];
        
        int i = left;
        int j = mid + 1;
        int k = 0;
        
        while(i <= mid && j <= right) {
            if(array[i] <= array[j]) {
                b[k] = array[i];
                i++;
            } else {
                b[k] = array[j];
                j++;
            }
            k++;
        }
        
        while(i <= mid) {
            b[k] = array[i];
            i++;
            k++;
        }
        
        while(j <= right) {
            b[k] = array[j];
            j++;
            k++;
        }
        
        for(int t = left, kk = 0; t < right - left + 1; ++t, ++kk) {
            array[t] = b[kk];
        }
        
    }

    /* I failed netflix because of this.
     * 2, 7, 5, 3, 1, 9
     * Let's say I want to insert 5, now num = 5, j starts at i - 1, which is 7. as long as it is larger than num, we keep copying 
     * a[j+1] = a[j], and now we have 2, which is smaller than 5, then we stop, we put 5 1 position behind it. 
     * 
     * */
    @Override
    public void insertionSort(int[] array) {
        if(array == null)
            return;
        
        int n = array.length;
        
        for(int i = 1; i < n; ++i) {
            int num = array[i];
            int j = i - 1;
            
            while(j >= 0 && array[j] > num) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = num;
        }
        
        System.out.println("insertion sort:");
        for(int i : array) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }

    /* http://en.wikipedia.org/wiki/Heapsort
     * Basically to use a max/min heap to sort, since insertion in heap is O(lgn), heap sort worst/avg is O(nlgn).
     * If use an array for heap, then this algorithm could be in-place without using any extra space. 
     * */
    @Override
    public void heapSort(int[] array) {
        // Using a heap, then it is not in place. 
         PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
         
         for(int i : array) {
             heap.add(i);
         }
         
         for(int i = 0; i < array.length; ++i) {
             array[i] = heap.poll();
         }
         
         for(int i : array) {
             System.out.print(i + " ");
         }
    }    
}
